from math import  log
import operator

def createDataSet1():    # 创造示例数据
    dataSet = [['高','长', '粗', '男'],
               ['高','短', '粗', '男'],
               ['矮','短', '粗', '男'],
               ['矮','长', '细', '女'],
               ['矮','短', '细', '女'],
               ['矮','短', '粗', '女'],
               ['矮','长', '粗', '女'],
               ['高','长', '粗', '女']]
    labels = ['身高','头发','声音']  #两个特征
    return dataSet,labels

def jisuanshang(dataset):
    numEntries=len(dataset)
    labelCounts={}  #字典
    for featVec in dataset:
        currentLabel=featVec[-1]
        if currentLabel not in labelCounts.keys():
            labelCounts[currentLabel]=0
        labelCounts[currentLabel]+=1
    shannonEnt=0.0
    for key in labelCounts:
        prop=float(labelCounts[key])/numEntries
        shannonEnt-=prop*log(prop,2)
    return  shannonEnt

def spliteDtaSet(dataset ,i ,value):   #寻找出在第i列的含有value的所有数据，返回一个不含这列的list,方便计算pi/p
    retDataSet = []
    for featVec in dataset:
        if featVec[i] == value:
            reducedFeatVec = featVec[:i]
            reducedFeatVec.extend(featVec[i + 1:])  #拼接后半部分
            retDataSet.append(reducedFeatVec)
    return  retDataSet

def chooseBestShang(dataset):  #选出最好的分类方式
    length=len(dataset[0])-1
    shang=jisuanshang(dataset)
    bestposition=-1
    bestshang=0
    for abcd in range(length):
        featList=[example[abcd] for example in dataset]
        uniList=set(featList)
        newShang=0
        for value in uniList:
            subdataste=spliteDtaSet(dataSet,abcd,value)
            prop=float(len(subdataste)/len(dataSet))
            newShang+=prop*jisuanshang(subdataste)
        jianxi=shang-newShang#信息增益越大越好
        if(jianxi>bestshang):
            bestshang=jianxi
            bestposition=abcd
    return bestposition

def createTree(dataSet,labels):
    classList=[example[-1] for example in dataSet]  # 类别：男或女
    if classList.count(classList[0])==len(classList):   #分类条件使用完   .count使用次数
        return classList[0]
    if len(dataSet[0])==1:    #只有一个分类
        return majorityCnt(classList)
    bestFeat=chooseBestShang(dataSet) #选择最优特征
    bestFeatLabel=labels[bestFeat]
    myTree={bestFeatLabel:{}} #分类结果以字典形式保存
    del(labels[bestFeat])
    featValues=[example[bestFeat] for example in dataSet]
    uniqueVals=set(featValues)
    for value in uniqueVals:
        subLabels=labels[:]
        myTree[bestFeatLabel][value]=createTree(spliteDtaSet(dataSet,bestFeat,value),subLabels)
    return myTree

def majorityCnt(classList):#结果又哪几种可能，返回可能最多的情况
    classCount = {}
    for vote in classList:
        if vote not in classCount.keys():
            classCount[vote] = 0
        classCount[vote] += 1
    sortedClassCount = sorted(classCount.items(), key=operator.itemgetter(1), reverse=True)  #reverse=True降序，false升序  items() 函数以列表返回可遍历的(键, 值) 元组数组。
    return sortedClassCount[0][0]

dataSet, labels=createDataSet1()
#print(jisuanshang(dataSet))
#print(spliteDtaSet(dataSet,1,"短"))
#print(chooseBestShang(dataSet))
#list=['男','女','男','女','女','女']
#print(majorityCnt(list))
#bestposition = chooseBestShang(dataSet)
#print(bestposition)
#print(jisuanshang(dataSet))
print(createTree(dataSet, labels))